package getOffer.offer38;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: wjy
 * @Date: 2021/11/29 13:36
 */
public class Solution {

    /**
     * 输入一个字符串，打印出该字符串中字符的所有排列。
     *
     * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
     *
     * 示例:
     *
     * 输入：s = "abc"
     * 输出：["abc","acb","bac","bca","cab","cba"]
     *
     * @param args
     */
    public static void main(String[] args) {

        String str = "abc";

        Solution solution = new Solution();
        String[] permutation = solution.permutation(str);

        for (String res : permutation) {
            System.out.println(res);
        }

    }

    List<String> list = new LinkedList<>();
    char[] chars;
    public String[] permutation(String s) {
        chars = s.toCharArray();
        this.dfs(0);
        return list.toArray(new String[list.size()]);
    }

    public void dfs(int m) {
        if (m == chars.length - 1) {
            list.add(String.valueOf(chars));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = m; i < chars.length; i++) {
            if (set.contains(chars[i])) {
                continue;
            }
            set.add(chars[i]);
            this.swap(i, m);
            dfs(m + 1);
            this.swap(i, m);
        }

    }

    public void swap(int a, int b) {
        char temp;
        temp = chars[a];
        chars[a] = chars[b];
        chars[b] = temp;
    }

}
